# 基础：
# 1. 二分工具
from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect

# 2. 数学计算：取整，取模，无限大，取对数； 统计工具包：statistics； 内建函数进制转换
from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e
# 统计相关： statistics： 均值， 方差， 标准差， 协方差
from statistics import mean
# 内建函数：进制转换： int(s:str, 16) 16进制转10进制 bin oct hex

# 3. 集合工具：  堆， 队列， 计数器， 双端队列； 内置集合： 列表list[]， 元组tuple()， 集合set()， 字典dict{}，
from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest
from collections import defaultdict, Counter, deque
from queue import PriorityQueue, Queue, LifoQueue
# 注意： 列表，元组的内部实现： 本质都是array
#       字典 旧版哈希表中元素会越来越稀疏

# 4. 字符串(正则表达式)  “”。join(a) a为字符串数组， 转换为字符串
# re.match, findall, sub, 正则表达式, re.findall(r'\d+', s:str) 返回s中的所有数字， ^ 头 $ 尾
import re
print("正则表达式exp: ", re.match(r'\d+', '123a4b').group())
print("正则表达式exp: ", re.findall(r'\d+', '123a4b'))

# 5. 输入输出处理：
# 内建函数： input() 获取键盘输入； input().split();  list(map(int, input() for _ in range(n)))
# 处理标准输入： import sys; for line in sys.stdin: a = line.split(); print(a[0])

# 6. 条件循环： for range();       三元表达式： return a = i if i > 0 else j
# 迭代工具： 排列，组合，分组，累积计算， 数对，合并数组对， 避免显式的for调用
from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise, product, zip_longest

# 7. 自定义函数(闭包，装饰器, 函数作为传递参数) & 匿名函数 lambda 表达式 + 内建函数map, filter, functools.reduce； sort(), sorted() 自定义排序
# 变量作用域相关： 内置函数：locals(), globals() 获取命名空间中的局部和全局变量和函数；
# 关键字： nonlocal(嵌套函数调用外部函数变量), global(函数调用类变量)
def func_namespace():
    x = 1
    print("局部变量： ", locals())
    print("全局变量： ", globals())
func_namespace()
global_var = 0
def change_alobal_var():
    global global_var
    global_var = 10
change_alobal_var()
print("全局变量： ", global_var)
def change_non_local_var():
    local_var = 0
    def inner_func():
        nonlocal local_var
        local_var = 10
    inner_func()
    return local_var
print("nonloal: ", change_non_local_var())
# 函数工具： reduce 类似map， 结合lambda 实现对迭代器元素的函数操作； @cahce内置缓存装饰器
# wraps: 装饰器工厂， partial: 纯函数方法， partial(cls_name, args*) 创建函数
from functools import lru_cache, cache, reduce, wraps, partial

# 8. 面向对象： 类， 抽象类， 元类， 继承，封装，多态
# super(), __init__ 常见魔术方法 __lt__, __call__,
# 多态和全局变量的修改

# 9. Python 模块化：定义Python包文件 __init__.py;  if __name__ == "__main__": import 时调用执行
# range: 数组切片； enumerate: 迭代器带索引取值； zip： 合并两个数组数对； map + lambda 类似reduce； filter + lambda 实现迭代器元素过滤
# 内建函数builtin: map, filter range, enumerate, zip

# 10. 异常处理 try & catch 语句， exception error

########################################################################################################################################
# 进阶
# 11. 对象的比较， 拷贝
# 12. Python中的参数传递， 值传递，应用传递：immutable 不可变对象

# 13. 装饰器： 函数一等公民 -> 装饰器, 修改原函数的功能，使得原函数不需要修改
# 带参装饰器； 类装饰器； 装饰器的嵌套

# 14. 元类 metaclass

# 15. 迭代器 & 生成器
# 容器 -> 迭代器 -> 生成器(特殊迭代器，降低内存占用, 提升程序效率)
# 生成器推导式： (x for x in range(2))
# yield 关键字替换 return

# Python 32: futures; 34: asyncio协程api 注解@asyncio.coroutine + yield from 关键字 ; 38: async + await 关键字

# 16. Python 协程： Python38之后 使用关键字 async 修饰函数，async def fun(): 构造协程
# t = threading.Thread(target = func()); t.start()
# p = Process(target = func()); p.start()

# 17. Python 并发编程Future: python
# from concurrent.futures import ProcessPoolExecutor; with ProcessPoolExecutor() as executor: res = executor.map(func, nums)
# from concurrent.futures import ThreadPoolExecutor; with ThreadPoolExecutor(max_workers=4) as executor: executor.map(func, nums)

# 18. Python 并发编程Asyncio:
# asyncio.get_event_loop().run_until_complete(coro1) 启动协程

# 19. Python GIL 全局解释器锁， 与多线程的关系
# 同步线程工具，使得任何时刻只能有一个线程在执行，即使在多核CPU上，Python线程也无法同时执行

# 20. Python 垃圾回收
# import gc && gc.collect() # 手动gc 返回回收的引用总数， 引用计数为主， 标记-清除，分代回收为辅

# 21. Python 内置模块调用：
# python -m dis exp.py > exp.txt # 输出exp.py的字节码到exp.txt
# python -m pip freeze > requirements.txt # 输出当前环境的依赖包名到req.txt

##################################################
# 规范
# 21. 代码风格
# 1. 编程风格： 禁用 from ... import ...; 禁止盲目使用列表生成式； is 比较对象地址； 遍历方式限制： dict对象禁用keys()方法：会在遍历时生成一个临时的列表，消耗大量内存且运行缓慢
# 2. 整合开发： linter

# 22. assert debug 工具， test工具； 防御性编程：输入合法校验； 不适用与run-time error的检查

# 23. 巧用上下文管理器和 with 语句精简代码，
# 资源管理操作： 必须保证在使用后释放，否则会资源泄露，系统处理缓慢，甚至崩溃
# 基于类__enter__(), __exit__(); 基于生成器 @contextlib.contextmanager

# 24. 单元测试： unitest.TestCase

# 25. pdb & cProfile 调试和性能分析
# pdb的必要性： 单一语言的IDE, 对混合代码不支持UI形式的，要求命令行形式的代码调试
# import pdb && pdb.set_trace()
# cProfile 性能分析： 计算每个模块消耗的时间
# import cProfile && cProfile。run()

# 26. 选择合适的异常处理方式


# sort() a.sort() + sort(key: lambda x :x, a) 实现自定义排序
# sorted() sorted(a)

# 三方： # pandas 依赖： numpy, pytz, six, tzdata, python-dateutils

# map, reduce, sorted, filter
from typing import List, Optional

from collections import Counter, defaultdict, deque
# Python 内置数据结构： dict: a = {}, a.setdefault(key, value); a.get(key, default)在key不存在时返回default; list(a.values()); list(a.items())
#                    defaultdict：





import sys

# sorted() list， str 排序
# "".join(arr) 数组字符串

# from sortedcontainers import SortedList, SortedDict, SortedSet

# pandas 依赖： numpy, pytz, six, tzdata, python-dateutils

sys.setrecursionlimit(10001000)

MOD = int(1e9 + 7)
INF = int(1e20)
INFMIN = float('-inf')  # 负无穷
INFMAX = float('inf')  # 正无穷
PI = 3.141592653589793
direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]
direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alps = 'abcdefghijklmnopqrstuvwxyz'

'''
heaqp
deque
permutations(arr,r) 返回的是一个长度为 r 的所有可能排列，无重复元素
combinations(arr,r) 返回的是一个长度为r的组合，它是有序的，无重复元素
bisect_left()等同 函数返回排序数组中值等于k的最左索引，如果没有，就返回插入后其索引
bisect()和bis_right函数返回排序数组中值等于k的最右索引+1，如果没有，就返回插入后其索引
gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写
startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引
isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接
eval() 字符串转换成列表、元组或者字典/
uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。
字典推倒式 {key: len(key) for key in list}
列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复
集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素
'''

# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符
def alp(i):
    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'

# lcm 最小公倍数 gcd 最大公约数
def lcm(x, y):
    return x * y // gcd(x, y)

# 快速幂
def qpow(x, y):
    ans = 1
    while y:
        if y & 1:
            ans *= x
        x *= x
        y >>= 1
    return ans

# 求组合数
def Comb(n, m, p):
    a = (factorial(n)) % p
    b = (qpow(factorial(m), (p - 2), p)) % p
    c = (qpow(factorial(n - m), (p - 2), p)) % p
    return a * b * c % p

# lucas求组合数
def Lucas(n, m, p):
    if m == 0:
        return 1
    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p


from bisect import bisect_left, bisect_right
from heapq import heapify
from itertools import pairwise, product

from typing import *
from math import *
import math
from heapq import *
from collections import *

def check(a, b):
    if a ** 2 > b ** 2 * 3.14:
        return "SQUARE"
    else:
        return "CIRCLE"
test = [6, 2], [12, 144]
class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        def count1(i:str) -> int:
            cnt = 0
            for s in i:
                if s == '1':
                    cnt += 1
            return cnt
        ans = []
        for i in nums:
            if count1(str(bin(i))) == k:
                ans.append(i)
        return sum(ans)

# 210II. 课程表： 有向图遍历，n*2的二维数组图表示
# 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
# 输出：[0,2,1,3]
class Solution1:
    # 1. dfs， 有向图遍历
    def findOrder1(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = defaultdict(list) # 有向图存储
        visited = [0] * numCourses # 标记每个节点的状态：0未访问；1访问中；2访问过
        res = [] # 数组模拟栈，0为栈底，n-1为栈顶
        valid = True # 判断图中是否有环

        for info in prerequisites: # 建图
            edges[info[1]].append(info[0])
        def dfs(u:int):
            nonlocal valid
            visited[u] = 1  # 访问中
            for v in edges[u]:
                if visited[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                elif visited[v] == 1:
                    valid = False
                    return
            visited[u] = 2
            res.append(u) # 节点入栈
        for i in range(numCourses):
            if valid and not visited[i]:
                dfs(i)
        if not valid:
            return list()
        return res[::-1] # 输入反序输出

    # 2. bfs
    def findOrder2(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = defaultdict(list) # 存储有向图
        indeg = [0] * numCourses # 存储每个节点的入度
        res = list()

        for info in prerequisites: # 建图
            edges[info[1]].append(info[0])
            indeg[info[0]] += 1
        q = deque([u for u in range(numCourses) if indeg[u] == 0]) # 节点入堆
        while q:
            u = q.popleft()
            res.append(u)
            for v in edges[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        if len(res) != numCourses:
            res = list()
        return res

# 743. 加权有向图, 最短路， n*3的二维数组图表示
# 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
# 输出：2
class Solution3:
    #
    def networkDelayTime1(self, times: List[List[int]], n: int, k: int) -> int:
        # n个节点， 邻接表表示加权有向图
        # 求从k节点出发到达所有节点时间
        g = [[float('inf')] * n for _ in range(n)]
        for x, y, time in times:
            g[x - 1][y - 1] = time

        dist = [float('inf')] * n
        dist[k - 1] = 0
        used = [False] * n
        for _ in range(n):
            x = -1
            for y, u in enumerate(used):
                if not u and (x == -1 or dist[y] < dist[x]):
                    x = y
            used[x] = True
            for y, time in enumerate(g[x]):
                dist[y] = min(dist[y], dist[x] + time)
        ans = max(dist)
        return ans if ans < float('inf') else -1

    # 2. 小根堆枚举
    def networkDelayTime2(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for x, y, time in times:
            g[x - 1].append((y - 1, time))

        dist = [float('inf')] * n
        dist[k - 1] = 0
        q = [(0, k - 1)]
        while q:
            time, x = heappop(q)
            if dist[x] < time:
                continue
            for y, time in g[x]:
                if (d := dist[x] + time) < dist[y]:
                    dist[y] = d
                    heappush(q, (d, y))

        ans = max(dist)
        return ans if ans < float('inf') else -1


# 2603 收集树中的金币， 无向图+节点值
# 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
# 输出：[0,2,1,3]
class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(coins)
        g = [[] for _ in range(n)]
        deg = [0] * n
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
            deg[x] += 1
            deg[y] += 1

        q = deque() # 拓扑排序，去掉没有金币的子树：
        for i, (d, c) in enumerate(zip(deg, coins)):
            if d == 1 and c == 0:
                q.append(i)
        while q:
            for y in g[q.popleft()]:
                deg[y] -= 1
                if deg[y] == 1 and coins[y] == 0:
                    q.append(y)

        for i, (d, c) in enumerate(zip(deg, coins)): # 再次topsort
            if d == 1 and c:
                q.append(i)
        if len(q) <= 1:
            return 0
        time = [0] * n
        while q:
            x = q.popleft()
            for y in g[x]:
                deg[y] -= 1
                if deg[y] == 1:
                    time[y] = time[x] + 1
                    q.append(y)
        return sum(time[x] >= 2 and time[y] >= 2 for x, y in edges) * 2

# 1928 规定时间内到达终点的最小花费(费用流)
# 输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
# 输出：11
class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:

        n = len(passingFees)
        f = [[float("inf")] * n for _ in range(maxTime + 1)]
        f[0][0] = passingFees[0]

        for t in range(1, maxTime + 1):
            for i, j, cost in edges:
                if cost <= t:
                    f[t][i] = min(f[t][i], f[t - cost][j] + passingFees[i])
                    f[t][j] = min(f[t][j], f[t - cost][i] + passingFees[j])
        ans = min(f[t][n - 1] for t in range(1, maxTime + 1))
        return -1 if ans == float("inf") else ans




# def t1():
#     global s
#     # nonlocal s
#     s += 1
#     print(s)
# s = 1
# t1()

if __name__ == '__main__':
    print('start...')
    a = [4,2,1]
    b = [1,2,3,4,5,6]
    edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]] # 邻接表
    values = [20, 10, 9, 7, 4, 3, 5] # 节点权值
    s = "01000111"
    ans = set()

    # 17. itertools 工具包
    # for i in groupby(b):
    #     print(i)
    #
    # for i in pairwise(b):
    #     print(i)
    #
    # for i in accumulate(b):
    #     print(i)

    # 16：建图
    # g = [[] for _ in range(max(max(i) for i in edges) + 1)]
    # for x, y in edges: # 无向图
    #     g[x].append(y)
    #     g[y].append(x)
    # print(g)
    #
    # g3 = [[] for _ in range(max(max(i) for i in edges) + 1)]
    # for x, y in edges: # 有向图
    #     g3[x].append(y)
    # print(g3)

    # g2 = defaultdict(list) # 有向图
    # for e in edges:
    #     g2[e[1]].append(e[0])
    # print(g2)
    # numCourses = 4;  prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
    # s = Solution1()
    # print(s.findOrder(numCourses, edges))



    # def check(s):
    #     if len(s) % 2 == 0:
    #         if '1' not in s[0: len(s) // 2] and '0' not in s[len(s) // 2:len(s)] or len(s) == 0:
    #             return True
    #     else:
    #         return False
    # for i in range(len(s)):
    #     for j in range(i, len(s)):
    #         if check(s[i:j+1]):
    #             ans.add(s[i:j+1])
    # res = 0
    # for s in ans:
    #     res = max(res, len(s))
    # print(res)

    # 15. dijkstra

    # 14. 二叉树层序遍历
    # def levelOrder(root) ->  List[int]:
    #     if root is None:
    #         return []
    #     ans = []
    #     cur = [root]
    #     while cur:
    #         nxt = [] # 临时数组，每次循环时初始化为空
    #         vals = []
    #         for node in cur:
    #             vals.append(node.val)
    #             if node.left: nxt.append(node.left)
    #             if node.right: nxt.append(node.right)
    #         cur = nxt
    #         ans.append(vals)
    #     return ans
        # q = deque([root]) # 队列
        # while q:
        #     vals = []
        #     for _ in range(len(q)):
        #         node = q.popleft() # 主动出队
        #         vals.append(node.val)
        #         if node.left: q.append(node.left)
        #         if node.right: q.append(node.right)
        #     ans.append(vals)
        # return  ans

    # 13. bfs 逃离火灾：2258：
    # grid = [[0, 2, 0, 0, 0, 0, 0], [0, 0, 0, 2, 2, 1, 0], [0, 2, 0, 0, 1, 2, 0], [0, 0, 2, 2, 2, 0, 2],
    #         [0, 0, 0, 0, 0, 0, 0]]
    # m, n = len(grid), len(grid[0])
    # def bfs(q:List[Tuple[int, int]]) -> (int, int, int): # 返回三个结果表示到达终点,左，上位置的最短时间
    #     time = [[-1] * n for _ in range(m)] # time[i][j]从q到达[i,j]的最短时间
    #     for i, j in q: # 起点
    #         time[i][j] = 0
    #     t = 1
    #     while q:
    #         tmp = q # 起点赋值给临时变量，便于枚举
    #         q = []
    #         for i, j in tmp:
    #             for x, y in (i-1,j), (i+1,j),(i,j-1),(i,j+1):
    #                 if 0<=x<m and 0<=y<n and grid[x][y]==0 and time[x][y] < 0:
    #                     time[x][y] = t # 每一的移动cost
    #                     q.append((x, y))
    #         t += 1
    #     return time[-1][-1], time[-1][-2], time[-2,-1]

    # 12.2262 字符串的总引力
    # s = "abbca"; res = 28
    # ans, sum_g, last = 0, 0, defaultdict()
    # for i, c in enumerate(s):
    #     a = last.get(c)
    #     sum_g += i - last.get(c, -1)
    #     ans += sum_g
    #     last.setdefault(c, i)
    #     # last[c] = i
    # print(ans)

    # 11. 邻接表建图 edges[List[List[int]]： 2925
    # g = [[] for _ in range(7)] # g[i]表示与点i相邻的点
    # for x, y in edges:
    #     g[x].append(y)
    #     g[y].append(x)
    # # print(g)
    # def dfs(i, p = -1): # 子树遍历： 根节点为i， i的父节点为j的子树的两种情况
    #     dp0, dp1 = 0, 0
    #     f = 0 # 标记位，有向图标记，避免遍历重复节点
    #     for j in g[i]:
    #         if j != p:
    #             j0, j1 = dfs(j, i)
    #             dp0 += j0
    #             dp1 += j1
    #             f = 1
    #     if not f: return values[i], 0
    #     return dp0 + values[i], max(dp1 + values[i], dp0)
    # print(dfs(0)[1])
    # print(sum(values))

    # 10. 哈希表& 字典：
    # a = {"a": 1, "b": 2, "c": 3, "a": 3}
    # a.setdefault(1, 2)
    # print(a)
    # b = a.get("a")
    # print(type(b))
    # print(a["a"])
    # b = defaultdict()

    # 9. set 创建集合
    # a = ('a','b','c')
    # print(type(a))
    # b = set()
    # c = set([0,1,2])
    # print(type(b))
    # print(c)
    # for i in c:
    #     b.add(i)
    # print(b)

    # 7. bisect_left, bisect_right , 有序数组a中插入target的下标：递增数组分别从左右开始
    # b = [1,2,2,3,4,5,6]
    # print(bisect_left(b, 2)) # 返回在b中首次出现b[i]>=2的元素的下标
    # print(bisect_right(b, 2)) # 返回在b中首次出现b[i]>2的元素下标

    # 6. product 指数型元素枚举
    # for x, y in product(a, b):
    #     print(x, y)
    # for x in product(a, repeat=3):
    #     print(x)

    # 5. 合并两个数组 zip
    # for x, y in zip(a, b):
    #     print(x, y)

    # 4. 统计01数组中1的个数：
    # c = [0,1,1,0,1]
    # print(sum(c)) # 求和
    # d = Counter(c) # Counter 计数器
    # c.count(1) # 数组count函数
    # print(d[1])
    # print(type(d))

    # 3. pairwise 相邻数对处理
    # for x, y in pairwise(a):
    #     print(x, y)

    # 1. heap utils:
    # Python 内置heap容器： from heapq import heapify, heappop, heappush, heappushpop, heapreplace
    a = [3, 2, 1]
    heapify(a) # 列表堆化， Python内置heapq中默认小顶堆
    heappop(a) # 返回最小值
    heappush(a, 4) # 向堆中添加新元素并维持有序结构
    heappushpop(a, 5) # 添加一个新元素并返回最小元素
    heapreplace(a, 6) # 返回最小元素并添加一个新元素
    print(a)
    # b = [(3,0), (2,2), (4,1), (6,3)]
    # h = []
    # for i in b:
    #     heappush(h, i)
    # print(h)
    # for _ in range(len(h)):
    #     print(heappop(h))
    # c = heapify(a)
    # #b = heappop(a)
    # heappush(a, 3)
    # print(a)
    #
    # for _ in range(len(a)):
    #     print(heappop(a))
    # print(b)

    # s = Solution()
    # print(s.sumIndicesWithKSetBits(nums = [5,10,1,5,2], k = 1))


    # 2. 交互式测试用例输入
    # for _ in range(int(input())):
    #     a, b = input().split()
    #     a = int(a)
    #     b = int(b)
    #     print(check(a, b))
    # for _ in range(int(input())):
    #     n, m = map(int, input().split())
    #     x = input()
    #     s = input()
    #     c = 0
    #     while s not in x and c < 10:
    #         x += x
    #         c += 1
    #     print(-1 if (c == 10 and s not in x) else c)
    #
    #
    # nums = [1, 5, 11, 5]
    # # nums.sort()
    # nums = sorted(nums, reverse=True)
    # print(nums)
    # for i in range(0, len(nums) + 1, -1):
    #     print(nums[i])

